package huawei.dfs;

import treenode.TreeNode;

/**
 * https://leetcode-cn.com/problems/house-robber-iii/submissions/
 * 重点:推到出动态规划的转换式
 * 每个节点有两种情况
 * unSelected, 获取左右子节点,两种情况更大值的和
 * selected: 只能使用子节点,未被选中的值
 */
public class J337 {
    public static void main(String[] args){
        TreeNode a = TreeNode.create(4, 1, -1, 2, -1, -1, -1, 3);
        a=TreeNode.create(3,4,5,1,3,-1,1);
        a=TreeNode.create(2,1,3,-1,4);
               a .show();
        System.out.println(rob(a));
    }
    public static int rob(TreeNode root) {
        int[] data =dfs(root);
        return Math.max(data[0],data[1]+root.val);
    }
    public static int[] dfs(TreeNode root){
        if(root==null){
            return new int[2];
        }
        int[] l=dfs(root.left);
        int[] r=dfs(root.right);

        // 0 表示选中, 1表示没选中,
        int selected = root.val + l[1] + r[1];
        int unSelected=Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        l[0]=selected;
        l[1]=unSelected;
        return l;
    }
}
